package Algorithm.Sort;

import java.util.Arrays;

/**
 * 双向选择排序：每一次从无序区间选出最小 + 最大的元素，存放在无序区间的最前和最后，直到全部待排序的数据元素排完 。
 * low:无序区间起始位置
 * high:无序区间终止位置
 * min：最小值索引
 * max:最大值索引
 */
public class SelectionSortOP {
    // 双向选择排序:能在一次循环中找到最大值和最小值并同时排序，增加了效率
//    双向选择排序：每一次从无序区间选出最小 + 最大的元素，存放在无序区间的最前和最后，直到全部待排序的数据元素排完 。
//    low:无序区间起始位置
//    high:无序区间终止位置
//    min：最小值索引
//    max:最大值索引
    public static void SelectionSortOP(int[] arr) {
        int low = 0;
        int high = arr.length - 1;

        // low = high,无序区间只剩下一个元素，整个数组已经有序
        while (low <= high) {
            // 定义max min为无序区间的起始位置索引
            int max = low;
            int min = low;
            // 无序区间
            // 找到集合中最大值和最小值
            for (int i = low + 1; i <= high; i++) {
                if (arr[i] < arr[min]) {
                    min = i;
                }
                if (arr[i] > arr[max]) {
                    max = i;
                }
            }
            // 将最大值和最小值分别放到区间的最后面和最前面
            int temp = arr[low];
            arr[low] = arr[min];
            arr[min] = temp;
            //如果最大值对应的索引刚好是无序区间的起始位置，经过上面的调整，最大值被调整到了arr[min]的位置
            if (max == low) {
                max = min;
            }
            int temp1 = arr[high];
            arr[high] = arr[max];
            arr[max] = temp1;
            high--;
            low++;
        }
    }

    public static void main(String[] args) {
        int[] arr = {2,1,5,3,7,8,4,9};
        SelectionSortOP(arr);
        System.out.println(Arrays.toString(arr));
    }
}
